package com.cheung.leetcode.day;

import  org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.day
 * @Author :  cheungming
 * @CreateTime : 2024-07-11 11:06:00
 * @Description : 每日 一题
 * @Version : 1.0
 */
public class Code2972Test {

    public long incremovableSubarrayCount(int[] nums) {
        // n 是
        int n = nums.length;
        if (n == 1) {
            return 1;
        }

        // 从左往右遍历，找到第一个不满足递增的元素
        int left = 0;
        while (left < n - 1 && nums[left] < nums[left + 1]) {
            left++;
        }

        // 一，特殊情况，如果数组是递增的，则删除所有元素，返回 n*(n+1)/2
        if (left == n - 1) {
            return (long) n * (n + 1) / 2;
        }


        // 一般情况
        long ans = 0;
        ans += (left + 2);
        // 二，一般情况 如何 6 5 7 8
        for (int right = n - 1; right > 0; right--) {
            // 从右往前遍历，如果不满足递增，则退出循环
            if (right < n - 1 && nums[right] >= nums[right + 1]) {
                break;
            }

            // 从左往右遍历，找到最大的小于右边界的元素
            while (left >= 0 && nums[left] >= nums[right]) {
                left--;
            }

            // 对于left到right之间的元素，[left+1,right-1]都是必须删除的，而0到left之间的元素，都是可以删除的
            // 因此需要删除的数组为 [left+1,right-1],[left,right-1],...,[0,right-1],共计 left+1-0+1 = left+2个

            ans += (left + 2);
        }

        return ans;
    }

    @Test
    public void test1() {
        assert incremovableSubarrayCount(new int[]{1, 2, 3, 4}) == 10;
    }

    @Test
    public void test2() {
        assert incremovableSubarrayCount(new int[]{6, 5, 7, 8}) == 7;
    }

    @Test
    public void test3() {
        assert incremovableSubarrayCount(new int[]{5, 5, 6}) == 5;
    }
}
